package code.classic150on2025;

import java.util.*;

public class DicTree {
    // 208. 实现 Trie (前缀树)
    class Trie {
        TrieNode root;

        public Trie() {
            root = new TrieNode();
        }

        public void insert(String word) {
            char[] chars = word.toCharArray();
            TrieNode node = root;
            for (char c : chars) {
                int pos = c - 'a';
                if (node.children[pos] == null) {
                    node.children[pos] = new TrieNode();
                }
                node = node.children[pos];
            }
            node.isEnd = true;
        }

        public boolean search(String word) {
            char[] chars = word.toCharArray();
            TrieNode node = root;
            for (char c : chars) {
                int pos = c - 'a';
                if (node.children[pos] == null)
                    return false;
                node = node.children[pos];
            }
            return node.isEnd;
        }

        public boolean startsWith(String prefix) {
            char[] chars = prefix.toCharArray();
            TrieNode node = root;
            for (char c : chars) {
                int pos = c - 'a';
                if (node.children[pos] == null)
                    return false;
                node = node.children[pos];
            }
            if (node.isEnd)
                return true;
            for (int i = 0; i < 26; i++) {
                if (node.children[i] != null)
                    return true;
            }
            return false;
        }
    }

    class TrieNode {
        public boolean isEnd;
        public TrieNode[] children;

        public TrieNode() {
            children = new TrieNode[26];
        }
    }

    // 211. 添加与搜索单词 - 数据结构设计
    class WordDictionary {

        WordDictNode root;

        public WordDictionary() {
            root = new WordDictNode();
        }

        public void addWord(String word) {
            char[] chars = word.toCharArray();
            WordDictNode node = root;
            for (char c : chars) {
                int index = c - 'a';
                if (node.children[index] == null)
                    node.children[index] = new WordDictNode();
                node = node.children[index];
            }
            node.isEnd = true;
        }

        public boolean search(String word) {
            return searchDFS(word, root, 0);
        }

        private boolean searchDFS(String word, WordDictNode root, int start) {
            int len = word.length();
            WordDictNode node = root;
            for (int i = start; i < len; i++) {
                char c = word.charAt(i);
                if (c == '.') {
                    boolean result = false;
                    for (int j = 0; j < 26; j++) {
                        if (node.children[j] != null)
                            result = result || searchDFS(word, node.children[j], i + 1);
                    }
                    return result;
                } else {
                    int index = c - 'a';
                    if (node.children[index] == null)
                        return false;
                    node = node.children[index];
                }
            }
            return node.isEnd;
        }
    }

    class WordDictNode {
        public boolean isEnd;
        public WordDictNode[] children;

        public WordDictNode() {
            children = new WordDictNode[26];
        }
    }

    // 212. 单词搜索 II
    public List<String> findWords(char[][] board, String[] words) {
        // 通过字典树回溯
        TrieTree trieTree = new TrieTree();
        for (String word : words) {
            trieTree.addWord(word);
        }
        List<String> list = new ArrayList<>();
        int m = board.length, n = board[0].length;
        boolean[][] visit = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                findWordsBackTrace(trieTree.root, board, i, j, list, visit);
            }
        }
        return list;
    }

    private void findWordsBackTrace(TrieTree.TrieTreeNode node, char[][] board, int i, int j, List<String> list, boolean[][] visit) {
        // 如果越界了或者访问过了，返回
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || visit[i][j])
            return;
        // 如果字典里没有这个，返回
        char c = board[i][j];
        if (node.children[c - 'a'] == null)
            return;
        // 回溯遍历
        visit[i][j] = true;

        node = node.children[c - 'a'];

        // 如果有这个字符，且是单词，加入答案，并把这个单词设置为false避免重复（也可以用set？）
        if (node.isEnd) {
            node.isEnd = false;
            list.add(node.word);
        }

        findWordsBackTrace(node, board, i + 1, j, list, visit);
        findWordsBackTrace(node, board, i - 1, j, list, visit);
        findWordsBackTrace(node, board, i, j + 1, list, visit);
        findWordsBackTrace(node, board, i, j - 1, list, visit);

        visit[i][j] = false;
    }

    class TrieTree {
        class TrieTreeNode {
            TrieTreeNode[] children;
            boolean isEnd;
            String word;
            public TrieTreeNode() {
                children = new TrieTreeNode[26];
            }
        }

        TrieTreeNode root;

        public TrieTree() {
            root = new TrieTreeNode();
        }

        public void addWord(String word) {
            char[] chars = word.toCharArray();
            TrieTreeNode node = root;
            for (char c : chars) {
                int index = c - 'a';
                if (node.children[index] == null)
                    node.children[index] = new TrieTreeNode();
                node = node.children[index];
            }
            node.isEnd = true;
            node.word = word;
        }
    }
}
